package offer;
import java.util.ArrayList;
import java.util.List;

/**
 * @author zhanb
 * @date 2020/5/21
 */
public class Solution57 {

    public static void main(String[] args) {
       /* int [] s = {10,26,30,31,47,60};
        int[] ints = twoSum2(s, 1);
        System.out.println(Arrays.toString(ints));*/
        int[][] ints = findContinuousSequence(9);
        for (int [] link : ints){
            for (int item :link){
                System.out.print(item+"\t");
            }
            System.out.println();
        }

    }

    /**
     * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[2,7] 或者 [7,2]
     * 输入：nums = [10,26,30,31,47,60], target = 40
     * 输出：[10,30] 或者 [30,10]
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        int [] result = new int [2];
        if(target<nums[0]) {
            return result;
        }
        boolean flag= false;
        //确定数组中比tager小的值的下标
        int index = 0;
        //如果数组中的最大值比tager小，那么就是全部匹配
        if(nums[nums.length-1] < target){
            index =nums.length-1;
        }else{
            //确定数组中比tager小的值的下标
            for (int i =0 ; i<nums.length ; i++){
                if(target<nums[i]){
                    index = i-1;
                    break;
                }
            }
        }
        //暴力匹配
        while (index>=1){
            //如果找到直接退出
            if(flag) {
                break;
            }
            for (int j =index-1 ; j>=0 ; j--) {
                if(target -nums[index] == nums[j]) {
                    result[0] = nums[j];
                    result[1] = nums[index];
                    flag = true;
                    //如果找到直接退出
                    break;
                }
            }
            index--;
        }
        return result;
    }


    /**
     * 1、初始化： 双指针 ii , jj 分别指向数组 numsnums 的左右两端 （俗称对撞双指针）。
     * 2、循环搜索： 当双指针相遇时跳出；
     * 计算和 s = nums[i] + nums[j]s=nums[i]+nums[j] ；
         * 若 s > targets>target ，则指针 jj 向左移动，即执行 j = j - 1j=j−1 ；
         * 若 s < targets<target ，则指针 ii 向右移动，即执行 i = i + 1i=i+1 ；
         * 若 s = targets=target ，立即返回数组 [nums[i], nums[j]][nums[i],nums[j]] ；
     * 3、返回空数组，代表无和为 targettarget 的数字组合。
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        //如果right过大可以先缩小
        /*if(nums[nums.length-1] < target)
            right =nums.length-1;
        else
            for (int i =0 ;  i<nums.length && right== 0; i++)
                if(target<nums[i])
                    right = i-1;*/
        while (leftIndex < rightIndex) {
            int sum = nums[leftIndex] + nums[rightIndex];
            if (sum < target) {
                leftIndex++;
            } else if (sum > target) {
                rightIndex--;
            } else {
                return new int[]{nums[leftIndex], nums[rightIndex]};
            }
        }
        return new int[0];
    }


    /**
     * 面试题57 - II. 和为s的连续正数序列
     * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
     * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
     *  输入：target = 9
     * 输出：[[2,3,4],[4,5]]
     *
     * 输入：target = 15
     * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
     *
     * @param target
     * @return
     */
    public static int[][] findContinuousSequence(int target) {
        // 滑动窗口的左边界
        int i = 1;
        // 滑动窗口的右边界
        int j = 1;
        // 滑动窗口中数字的和
        int sum = 0;
        List<int[]> res = new ArrayList<>();
        while (i <= target / 2) {
            if (sum < target) {
                // 右边界向右移动
                sum += j;
                j++;
            } else if (sum > target) {
                // 左边界向右移动
                sum -= i;
                i++;
            } else {
                // 记录结果
                int[] arr = new int[j-i];
                for (int k = i; k < j; k++) {
                    arr[k-i] = k;
                }
                res.add(arr);
                // 左边界向右移动
                sum -= i;
                i++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}


